package com.g02.hj;

import com.g02.qt.ListNode;

public class KReverse {
    static ListNode reverse(ListNode head) {
        // 单独实现一个链表反转的代码
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        // 先确定有 a 个组需要反转
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        int a = len / k;
        cur = head;
        ListNode nh = null;
        ListNode end = new ListNode(-1);
        while (a > 0) {
            // 选出一节
            ListNode p = cur;
            for (int i = 0; i < k - 1; i++) {
                cur = cur.next;
            }
            ListNode next = cur.next;
            cur.next = null;
            cur = next;
            // 将选出的一节反转
            ListNode p1 = reverse(p);
            // 进行拼接
            if (nh == null) {
                nh = p1;
                end = p;
            } else {
                end.next = p1;
                end = p;
            }
            // 反转完成一组，待完成减一
            a--;
        }
        // 将最后不足反转的直接接到末尾
        end.next = cur;
        return nh;
    }
}
